#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution
{
public:
  // 这题和39题组合的相同点是：你不能出现重复的元素序列，即使你的顺序不同，eg:for [2,3,6,7]:[2,2,3][2,3,2]
  // 如何避免：39和40都需要用到一个就是，在每一次for循环push元素给track时，起始点start是上一次迭代进入循环的i,因此[2,3]知乎只能选到3,6,7,因为一开始序列排序了(在一个for循环中，所有被遍历到的数都是属于一个层级的，在树中体现为同一层)

  // 而在46.全排列中不存在这样的考虑：因为数字不能重复用，在回溯前后增加visited标志位即可

  // 本题虽然元素也只能使用一次, 但是序列中有重复元素，这话相当于没说，用了1'与1''不等于重复用元素，准确来说应该说每个位置上的数只用一次

  // 本题要求：[1 2' 2'' 2''' 5]
  //1. 不能包含重复的组合：通过39的手段，先对candidates排序，然后那就按照顺序依次减去数组中的元素，递归求解即可(即i=start)
  //2. 1-2'-(2''/2'''/5)与1-2''-(2'''/5) 后者的选择范围没有前者大，应该剪枝：candidates[i-1]==candidates[i] 与 i>index
  vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
  {
    // “剪枝”的前提是排序，升序或者降序均可
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> track;
    dfs(res, track, candidates, target, 0, 0);
    return res;
  }

  void dfs(vector<vector<int>> &res, vector<int> &track, vector<int> &candidates, int target, int depth, int sum)
  {
    // index >= input.size() ，写成 index == input.size() 即可
    // 因为每次都 + 1，在 index == input.size() 剪枝就可以了

    // 递归出口 递归到target和剪枝都在这了，多了index
    if (sum > target)
    {
      return;
    }
    if (sum == target)
    {
      res.push_back(track);
      return;
    }
    if (depth == candidates.size() - 1)
    {
      return;
    }

    // 递归方程
    for (int i = depth; i < candidates.size(); i++)
    {

      // 【我添加的代码在这里】：
      // 1、i > index 表明剪枝的分支一定不是当前层的第 1 个分支
      // 2、input[i - 1] == input[i] 表明当前选出来的数等于当前层前一个分支选出来的数
      // 因为前一个分支的候选集合一定大于后一个分支的候选集合
      // 故后面出现的分支中一定包含了前面分支出现的结果，因此剪枝
      // “剪枝”的前提是排序，升序或者降序均可
      if (i > depth && candidates[i - 1] == candidates[i])
      {
        continue;
      }

      if (sum + candidates[i] > target)
      {
        break; // 剪枝
      }
      // 选择
      track.push_back(candidates[i]);
      sum += candidates[i];
      dfs(res, track, candidates, target, i + 1, sum);
      // 撤销
      track.pop_back();
      //sum-=candidates[i];
    }
    return;
  }
};

int main()
{
  Solution solute;
  vector<int> nums = {10, 2, 3, 3, 5};
  int target = 5;
  solute.combinationSum2(nums, target);
  return 0;
}